package leetcode.code1300;

import java.util.stream.Stream;

public class Solution {

	public int findBestValue(int[] arr, int target) {
		int max = Integer.MIN_VALUE, sum = 0;
		for (int i = 0; i < arr.length; i++) {
			max = Math.max(max, arr[i]);
			sum += arr[i];
		}
		if (sum <= target) {
			return max;
		}
		int[] ans1 = this.f1(arr, target);
		if (ans1[0] == target) {
			return ans1[1];
		}
		int[] ans2 = this.f2(arr, target);
		return Math.abs(ans1[0] - target) <= Math.abs(ans2[0] - target) ? ans1[1] : ans2[1];
	}

	private int[] f1(int[] arr, int target) {
		// sum<=target
		int l = 0, r = (int) 1e5 + 1;
		int ans = 0, t = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			long sum = 0;
			for (int i = 0; i < arr.length; i++) {
				if (arr[i] > mid) {
					sum += mid;
				} else {
					sum += arr[i];
				}
			}
			if (sum <= target) {
				ans = mid;
				t = (int) sum;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		return new int[] { t, ans };
	}

	private int[] f2(int[] arr, int target) {
		// sum>=target
		int l = 0, r = (int) 1e5 + 1;
		int ans = 0, t = 0;
		while (l <= r) {
			int mid = l + ((r - l) >> 1);
			long sum = 0;
			for (int i = 0; i < arr.length; i++) {
				if (arr[i] > mid) {
					sum += mid;
				} else {
					sum += arr[i];
				}
			}
			if (sum >= target) {
				ans = mid;
				t = (int) sum;
				r = mid - 1;
			} else {
				l = mid + 1;
			}
		}
		return new int[] { t, ans };
	}

}
